在集成学习之Adaboost算法原理介绍中，我们对Boosting家族的Adaboost算法做了总结，本文就对Boosting家族中另一个重要的算法梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT)做一个总结。GBDT有很多简称，有GBT（Gradient Boosting Tree）, GTB（Gradient Tree Boosting ）， GBRT（Gradient Boosting Regression Tree）, MART(Multiple Additive Regression Tree)，其实都是指的同一种算法，本文统一简称GBDT。GBDT在BAT大厂中也有广泛的应用，假如要选择3个最重要的机器学习算法的话，个人认为GBDT应该占一席之地。
GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。回顾下Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。
在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是 $f_{t-1}(x)$ ，损失函数是 $L\left(y, f_{t-1}(x)\right)$ ，我们本轮迭代的目标是找到一个CART回归树模型的弱 学习器 $h_t(x)$ ，让本轮的损失函数 $L\left(y, f_t(x)\right)=L\left(y, f_{t-1}(x)+h_t(x)\right)$ 最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。
GBDT的思想可以用一个通俗的例子解释，假如有个人 30 岁，我们首先用 20 岁去拟合，发现损失有 10 岁，这时我们用6岁去拟合剩下的损失，发现差距 还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。 从上面的例子看这个思想还是蛮简单的，但是有个问题是这个损失的拟合不好度量，损失函数各种各样，怎么找到一种通用的拟合方法呢?
在上一节中，我们介绍了GBDT的基本思路，但是没有解决损失函数拟合方法的问题。针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合 本轮损失的近似值，进而拟合一个CART回归树。第t轮的第 1 个样本的损失函数的负梯度表示为 $$ r_{t i}=-\left[\frac{\left.\partial L\left(y_i, f\left(x_i\right)\right)\right)}{\partial f\left(x_i\right)}\right]_{f(x)=f_{t-1}(x)} $$ 利用 $\left(x_i, r_{t i}\right)(i=1,2, \ldots m)$, 我们可以拟合一颗CART回归树，得到了第颗回归树，其对应的叶节点区域 $R_{t j}, j=1,2, \ldots, J$ 。其中J为叶子节 点的个数。 针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的的输出值 $c_{t j}$ 如下: $$ c_{t j}=\underbrace{\arg \min }_c \sum_{x_i \in R_{t j}} L\left(y_i, f_{t-1}\left(x_i\right)+c\right) $$ 这样我们就得到了本轮的决策树拟合函数如下: $$ h_t(x)=\sum_{j=1}^J c_{t j} I\left(x \in R_{t j}\right) $$
从而本轮最终得到的强学习器的表达式如下: $$ f_t(x)=f_{t-1}(x)+\sum_{j=1}^J c_{t j} I\left(x \in R_{t j}\right) $$ 通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟 合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。
好了，有了上面的思路，下面我们总结下GBDT的回归算法。为什么没有加上分类算法一起? 那是因为分类算法的输出是不连续的类别值，需要一些处 理才能使用负梯度，我们在下一节讲。 输入是训练集样本 $T=\left\{\left(x, y_1\right),\left(x_2, y_2\right), \ldots\left(x_m, y_m\right)\right\}$ ， 最大迭代次数 $T$ ， 损失函数 $L_{\circ}$ 输出是强学习器 $f(x)$
b)利用 $\left(x_i, r_{t i}\right)(i=1,2, \ldots m)$ ，拟合一颗CART回归树, 得到第颗回归树，其对应的叶子节点区域为 $R_{t j}, j=1,2, \ldots, J$ 。其中J为回归树t 的叶子节点的个数。 c) 对叶子区域 $j=1,2, . . J$, 计算最佳拟合值 $$ c_{t j}=\underbrace{\arg \min }_c \sum_{x_i \in R_{t j}} L\left(y_i, f_{t-1}\left(x_i\right)+c\right) $$ d) 更新强学习器 $$ f_t(x)=f_{t-1}(x)+\sum_{j=1}^J c_{t j} I\left(x \in R_{t j}\right) $$
为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数 的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。
对于二元GBDT，如果用类似于逻辑回归的对数似然损失函数，则损失函数为: $$ L(y, f(x))=\log (1+\exp (-y f(x))) $$ 其中 $y \in\{-1,+1\}$ 。则此时的负梯度误差为 $$ r_{t i}=-\left[\frac{\left.\partial L\left(y, f\left(x_i\right)\right)\right)}{\partial f\left(x_i\right)}\right]_{f(x)=f_{t-1}(x)}=y_i /\left(1+\exp \left(y_i f\left(x_i\right)\right)\right) $$ 对于生成的决策树，我们各个叶子节点的最佳负梯度拟合值为 $$ c_{t j}=\underbrace{\arg \min }_c \sum_{x_i \in R_{t j}} \log \left(1+\exp \left(-y_i\left(f_{t-1}\left(x_i\right)+c\right)\right)\right) $$ 由于上式比较难优化，我们一般使用近似值代替 $$ c_{t j}=\sum_{x_i \in R_{t j}} r_{t i} / \sum_{x_i \in R_{t j}}\left|r_{t i}\right|\left(1-\left|r_{t i}\right|\right) $$ 除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。
多元GBDT要比二元GBDT复杂一些，对应的是多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为 $K$ ，则此时我们的对数似然损失函数为: $$ L(y, f(x))=-\sum_{k=1}^K y_k \log p_k(x) $$ 其中如果样本输出类别为 $\mathrm{k}$ ，则 $y_k=1$ 。第 $\mathrm{k}$ 类的概率 $p_k(x)$ 的表达式为:
$$ p_k(x)=\exp \left(f_k(x)\right) / \sum_{l=1}^K \exp \left(f_l(x)\right) $$集合上两式，我们可以计算出第 $t$ 轮的第 $i$ 个样本对应类别 $l$ 的负梯度误差为 $$ r_{t i l}=-\left[\frac{\left.\partial L\left(y_i, f\left(x_i\right)\right)\right)}{\partial f\left(x_i\right)}\right]_{f_k(x)=f_{l, t-1}(x)}=y_{i l}-p_{l, t-1}\left(x_i\right) $$ 观察上式可以看出，其实这里的误差就是样本 $i$ 对应类别 $l$ 的真实概率和 $t-1$ 轮预测概率的差值。 对于生成的决策树，我们各个叶子节点的最佳负梯度拟合值为 $$ c_{t j l}=\underbrace{\arg \min }_{c_{j l}} \sum_{i=0}^m \sum_{k=1}^K L\left(y_k, f_{t-1, l}(x)+\sum_{j=0}^J c_{j l} I\left(x_i \in R_{t j l}\right)\right) $$ 由于上式比较难优化，我们一般使用近似值代替 $$ c_{t j l}=\frac{K-1}{K} \frac{\sum_{x_i \in R_{t j l}} r_{t i l}}{\sum_{x_i \in R_{t i l}}\left|r_{t i l}\right|\left(1-\left|r_{t i l}\right|\right)} $$ 除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同。 GBDT常用损失函数 这里我们再对常用的GBDT损失函数做一个总结。 对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种:
d) 分位数损失。它对应的是分位数回归的损失函数，表达式为 $$ L(y, f(x))=\sum_{y \geq f(x)} \theta|y-f(x)|+\sum_{y<f(x)}(1-\theta)|y-f(x)| $$ 其中 $\theta$ 为分位数，需要我们在回归前指定。对应的负梯度误差为: $$ r\left(y_i, f\left(x_i\right)\right)= \begin{cases}\theta & y_i \geq f\left(x_i\right) \\ \theta-1 & y_i<f\left(x_i\right)\end{cases} $$ 对于Huber损失和分位数损失，主要用于健壮回归，也就是减少异常点对损失函数的影响。
和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式。 第一种是和Adaboost类似的正则化项，即步长(learning rate)。定义为 $\nu$, 对于前面的弱学习器的迭代 $$ f_k(x)=f_{k-1}(x)+h_k(x) $$ 如果我们加上了正则化项，则有 $$ f_k(x)=f_{k-1}(x)+\nu h_k(x) $$ $\nu$ 的取值范围为 $0<\nu \leq 1$ 。对于同样的训练集学习效果，较小的 $\nu$ 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
第二种正则化的方式是通过子采样比例 (subsample) 。取值为 $(0,1]$ 。 注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是 不放回抽样。如果取值为 1 ，则全部羘本都使用，等于没有使用子采样。如果取值小于 1 ，则只有一部分样本会去做 $G B D T$ 的决策树拟合。选择小于的比例可以减 少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推龿在 $[0.5,0.8]$ 之间。 使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree，SGBT)。由于使用了子采样，程序可以通过采样分发到不同 的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。 第三种是对于弱学习器即CART回归树进行正则化剪枝。在决策树原理篇里我们已经讲过，这里就不重复了。
GBDT终于讲完了，GDBT本身并不复杂，不过要吃透的话需要对集成学习的原理，决策树原理和各种损失函树有一定的了解。由于GBDT的卓越性能， 只要是研究机器学习都应该掌握这个算法，包括背后的原理和应用调参方法。目前GBDT的算法比较好的库是xgboost。当然scikit-learn也可以。 最后总结下GBDT的优缺点。 GBDT主要的优点有:
转载自：